package interview;

import java.util.Random;

public class Interview_day3 {

	/**
	 * Just similar to word ladders in leetcode (see LeetCode_day16)
	 * @param dic
	 * @param source
	 * @param target
	 */
	public static void transformWord(String[] dic, String source, String target){
		//build adjacency list
		
	}
	

	/**
	 * Given [a1,a2,...,an,b1,b2,...,bn,c1,c2,...,cn] and convert it to
	 * [a1,b1,c1,...,an,bn,cn] in-place
	 * 
	 * The problem can be seen as:
	 * Turn the original array into a 3 * N matrix
	 * Just want the transpose of this matrix
	 * 
	 * @param a
	 */
	public static void convertArray(int[] a){
		int n = a.length / 3;
		for(int i= 0 ; i < a.length ; i++){
			int swapIndex = (i % 3) * n + i/3;
			while(swapIndex < i)
				swapIndex = (swapIndex % 3) * n + swapIndex/3 ;
			if(i != swapIndex){
				a[i] = a[swapIndex] ^ a[i];
				a[swapIndex] = a[swapIndex] ^ a[i];
				a[i] = a[swapIndex] ^ a[i];
			}
		}
		
		System.out.println();
		for(int i : a)
			System.out.print(i + " ");
		System.out.println();
	}
	
	
	/**
	 * The random selection of partition in quick-sort
	 * 
	 * @param a
	 * @param k
	 */
	public static int kthLargestElementInArray(int[] a, int start, int end, int k){
		if(start < end){
			Random ran = new Random();
			int q = ran.nextInt(end-start+1)+start;
			//swap
			a[end] = a[end] ^ a[q];
			a[q] = a[end] ^ a[q];
			a[end] = a[end] ^ a[q];
			
			int ind = 0;
			for(int i = start ; i < end ; i++){
				if(a[i] < a[end]){
					if(i != ind){//swap
						a[i] = a[i] ^ a[ind];
						a[ind] = a[i] ^ a[ind];
						a[i] = a[i] ^ a[ind];
					}
					ind++;
				}
			}
			if(ind == k-1) return a[end];
			else{
				a[ind] = a[ind] ^ a[end];
				a[end] = a[ind] ^ a[end];
				a[ind] = a[ind] ^ a[end];
				
				if(ind < k-1)
					return kthLargestElementInArray(a, ind+1, end, k-ind-1);
				else return kthLargestElementInArray(a, start, ind-1, k);
			}
		}
		return -1;
	}
	
	/**
	 * Given two strings s1 and s2, determine whether s1 is a rotated version of s2
	 * 
	 * @param s1
	 * @param s2
	 */
	
	public static void isRotateString(String s1, String s2){
		if(s1.length() != s2.length()) System.out.println("false");
		else{
			if((s1 + s1).indexOf(s2) == -1) System.out.println("false");
			else System.out.println("true");
		}
	}
	
	/**
	 * Ugly numbers are numbers whose only prime factors are 2, 3 or 5. 
	 * The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
	 * shows the first 11 ugly numbers. By convention, 1 is included.
	 * Write a program to find and print the 150′th ugly number.
	 * @param n
	 */
	public static void uglyNumbers(int n){
		int[] res = new int[n];
		res[0] = 1;
		if(n == 1){
			System.out.println(res[n-1]);
		}else{
			int ind1 = 0, ind2 = 0, ind3 = 0;
			for(int i = 1 ; i < n ; i++){
				int r1 = res[ind1] * 2;
				int r2 = res[ind2] * 3;
				int r3 = res[ind3] * 5;
				
				if(r1 < r2 && r1 < r3){
					res[i] = r1;
					r1++;
				}else if(r2 < r1 && r2 < r3){
					res[i] = r2;
					r2++;
				}else if(r3 < r1 && r3 < r2){
					res[i] = r3;
					r3++;
				}
			}
			System.out.println(res[n-1]);
		}
	}
	
	
	public static void main(String[] args) {
		System.out.println(kthLargestElementInArray(new int[]{2,3,4,1,6,5}, 0, 5, 4));
		convertArray(new int[]{1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7});
	}

}
